package algorithm;

/**
 * 斐波那契 1、1、2、3、5、8、13、21、34、55
 */
public class Fibonacci {

    /**
     * 递归实现斐波那契,事件复杂度较高
     * @param n
     * @return
     */
    public static int fbNum(int n){
        if (n == 1 || n == 2)
            return 1;
        else
            return fbNum(n-1)+fbNum(n-2);
    }

    /**
     * 循环实现斐波那契
     * @param n
     * @return
     */
    public static int fbForNum(int n){
        if (n == 1 || n == 2)
            return 1;
        int lastLast = 1; //定义变量 前前项,因为从3开始,所以默认值是1
        int last = 1;//定义变量 前项,因为从3开始,所以默认值是1
        int sum = 2;//定义当前项

        for (int i = 3;i <= n; i++){
            sum = lastLast + last;//前两项的值相加得到第三项的值
            lastLast = last;//把前项的值赋值给前前项,此时前项相当于第二次循环时的前前项
            last = sum;//当前项的值赋给前项,此时当前项相当于第二次循环时的前项
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(fbNum(10));
        System.out.println(fbForNum(10));
    }
}
